#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <set>
using namespace std;

//#define READ_FILE

struct SignalPair
{
	short left, right;
};

struct SignalNode
{
	vector<SignalPair> signal[15];
};

SignalNode g_nodes[10];
#define _(c) g_nodes[(c)-'a']

vector<SignalNode*> g_tree;
set<int> g_neededSignalForLeaf;



void fillNeededSignalForEachNode(int index, int signalCount, int validCount, int totalCount, vector< set<int> >& neededSignal)
{
	set<int>* lNeededSignal;
	set<int>* rNeededSignal;

	int lChildIndex = index + index + 1;
	int rChildIndex = index + index + 2;

	if (lChildIndex >= totalCount || g_tree[lChildIndex] == NULL)
	{
		lNeededSignal = &g_neededSignalForLeaf;
		rNeededSignal = &g_neededSignalForLeaf;
	}
	else
	{
		lNeededSignal = &(neededSignal[lChildIndex]);
		rNeededSignal = &(neededSignal[rChildIndex]);
	}

	SignalNode& node = *g_tree[index];

	for (int i = 0; i < signalCount; ++i)
	{
		vector<SignalPair>& vp = node.signal[i];

		for (unsigned int j = 0; j < vp.size(); ++j)
		{
			int l = vp[j].left;
			int r = vp[j].right;

			if (lNeededSignal->find(l) != lNeededSignal->end() &&
			        rNeededSignal->find(r) != rNeededSignal->end())
			{
				neededSignal[index].insert(i);
				break;
			}
		}
	}
}

bool isValid(int signalCount, int validCount, int totalCount)
{
	vector< set<int> > neededSignal;
	set<int> s;
	neededSignal.insert(neededSignal.begin(), totalCount, s);
	
	for (int i = totalCount - 1; i >= 0; --i)
	{
		if (g_tree[i] == NULL)
		{
			continue;
		}

		fillNeededSignalForEachNode(i, signalCount, validCount, totalCount, neededSignal);

		if (neededSignal[i].size() == 0)
		{
			return false;
		}
	}

	if (neededSignal[0].find(0) != neededSignal[0].end())
	{
		return true;
	}
	else
	{
		return false;
	}
}


int main()
{
#ifdef READ_FILE
	ifstream readIn("1011.input");

	if (!readIn)
	{
		readIn.open("../1011.input");
	}

#else
#define readIn cin
#endif

	int NTACount = 0;

	while (true)
	{
		NTACount++;

		int n, m, k;
		readIn >> n >> m >> k;

		if (n == 0 && m == 0 && k == 0)
		{
			break;
		}

		if (NTACount > 1)
		{
			cout << endl;
		}
		cout << "NTA" << NTACount << ":\n";

		// clean global variable

		for (int i = 0; i < 10; ++i)
		{
			for (int j = 0; j < 15; ++j)
			{
				g_nodes[i].signal[j].clear();
			}
		}
		
		g_neededSignalForLeaf.clear();
		for (int i = 0; i < m; ++i)
		{
			g_neededSignalForLeaf.insert(n - 1 - i);
		}




		// read in signal table

		while (readIn.get() != '\n'); // clean the EOL

		for (int j = 0; j < n; ++j)
		{
			for (int i = 0; i < k; ++i)
			{
				SignalPair p;
				string line;
				getline(readIn, line);
				istringstream strIn(line);

				while (!strIn.eof())
				{
					strIn >> p.left >> p.right;
					g_nodes[i].signal[j].push_back(p);
				}
			}
		}


		////////////////////////////////////////////////////////
		/* For Test
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < k; ++j)
			{
				vector<SignalPair>& p = g_nodes[j].signal[i];
				for (unsigned int c = 0; c < p.size(); c++)
				{
					cout << "(" << p[c].left << ", " << p[c].right << ")";
				}
				cout << '\t';
			}
			cout << endl;
		}
		//*////////////////////////////////////////////////////////

		
		// read in tree and calculate

		int levelCount;
		readIn >> levelCount;

		while (levelCount != -1)
		{
			g_tree.clear();

			int totalCount = (1 << (levelCount + 1)) - 1; // 2^(levelCount+1) - 1


			for (int i = 0; i < totalCount; ++i)
			{
				char ch;
				readIn >> ch;

				if (ch == '*')
				{
					g_tree.push_back(NULL);
				}
				else
				{
					g_tree.push_back(&_(ch));
				}

			}

			//////////////////////////////////////////////////
			/* For Test
			cout << g_tree.size() << endl;
			for (unsigned int i = 0; i < g_tree.size(); ++i)
			{
				if (g_tree[i] == NULL)
				{
					cout << "*  ";
				}
				else
				{
					cout << g_tree[i]->signal[0][0].left << "  ";
				}
			}
			//*/////////////////////////////////////////////////

			bool res = isValid(n, m, totalCount);

			if (res)
			{
				cout << "Valid\n";
			}
			else
			{
				cout << "Invalid\n";
			}

			readIn >> levelCount;
		}

	}

	return 0;
}
